import java.util.Stack;

/**
 * Created with IntelliJ IDEA
 * Details about unstoppable_t:
 * User: Administrator
 * Date: 2021-03-24
 * Time: 14:47
 */
class BTNode {
    public char val;
    public BTNode left;//左子树的引用
    public BTNode right;//右子树的引用

    public BTNode(char val) {
        this.val = val;
    }
}

public class BianryTraversal {
    /*
    前序遍历 非递归实现  好理解但代码长 递归思路稍微绕一点 代码短
     */
    void preOrderTraversal1(BTNode root){
        Stack<BTNode> stack = new Stack<>();
        if(root == null) return ;
        BTNode cur = root; //让cur指向最开始的根结点，往后遍历

        while(cur != null || !stack.empty()){
            while(cur != null){
                //cur不为空，将其压入栈中
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            //循环出来说明cur为空
            BTNode top = stack.pop(); //让top指向栈顶弹出的元素
            cur = top.right;
        }
    }

    /*
    中序遍历 非递归实现
     */
    void inOrderTraversal1(BTNode root){
        Stack<BTNode> stack = new Stack<>();
        if(root == null) return ;
        BTNode cur = root; //让cur指向最开始的根结点，往后遍历

        while(cur != null || !stack.empty()){
            while(cur != null){
                //cur不为空，将其压入栈中
                stack.push(cur);
                cur = cur.left;
            }
            //循环出来说明cur为空
            BTNode top = stack.pop(); //让top指向栈顶弹出的元素
            System.out.print(top.val + " "); //左子树判断完打印根结点
            cur = top.right;
        }

    }

    /*
    后序遍历 非递归实现  需要注意
     */
    void postOrderTraversal1(BTNode root){
        Stack<BTNode> stack = new Stack<>();
        if(root == null) return ;
        BTNode cur = root; //让cur指向最开始的根结点，往后遍历
        BTNode prev = null;

        while(cur != null || !stack.empty()){
            while(cur != null){
                //cur不为空，将其压入栈中
                stack.push(cur);
                cur = cur.left;
            }
            //循环出来说明cur为空
            BTNode top = stack.peek(); //让top指向结点的右子树可能不为空,所以不能直接pop
            //当top右边为空时或者此时需要打印top的右边已经打印过
            if(top.right == null || top.right == prev){
                stack.pop();
                System.out.print(top.val + " ");
                prev = top;  //top打印过就用prev存起来
            }else{
                cur = top.right;
            }
        }
    }
}
